package com.itheima.algorithm.recursion_single;

public class E05InsertionSort {
    public static void sort(int [] a){
         insertion(a,1);
    }

    //low表示未排序数组的左边界
    public static void insertion(int [] a,int low){
        //当low==a.length表示没有未排序数组元素了，当low==a.length-1表示还有一个元素未排序
        if(low == a.length){
            return;
        }
        //变量t记录要排序元素
        int t=a[low];
        //已排序指针右指针
        int i=low-1;

        while(i>=0 && a[i]>t){
            a[i+1]=a[i];
            i--;
        }

        //找到插入位置
        if(i+1!=low){
            a[i+1]=t;
        }

        insertion(a,low+1);
    }
}
